from c06_tree.utils import TreeNode


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        arr = []
        def pre(root):
            if not root:
                arr.append('#')
            else:
                arr.append(str(root.val))
                pre(root.left)
                pre(root.right)
        pre(root)
        return ','.join(arr)


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        data = data.split(',')
        i = 0
        def rebuild():
            nonlocal i
            if data[i] == '#':
                return None
            root = TreeNode(int(data[i]))
            i += 1
            root.left = rebuild()
            i += 1
            root.right = rebuild()
            return root
        return rebuild()

    def serialize2(self, root):
        arr = []
        def post(root):
            if not root:
                arr.append('#')
            else:
                post(root.left)
                post(root.right)
                arr.append(str(root.val))
        post(root)
        return ','.join(arr)


    def deserialize2(self, data):
        # 后续序列化，还得先建头
        data = data.split(',')
        i = len(data) - 1
        def rebuild():
            nonlocal i
            if data[i] == '#':
                return None
            root = TreeNode(int(data[i]))
            i += 1
            root.right = rebuild()
            i += 1
            root.left = rebuild()
            return root
        return rebuild()

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))